/*
 * BinarySortTree.cpp
 *
 *  Created on: 2014年5月10日
 *      Author: rock
 */

#include "BinarySortTree.h"
#include <iostream>


Node::Node(int data)
{
	this->m_data = data;
	this->m_right = NULL;
	this->m_left = NULL;
}

Node::~Node()
{
	if(m_left != NULL)
	{
		delete m_left;
		m_left = NULL;
	}

	if(m_right != NULL)
	{
		delete m_right;
		m_right = NULL;
	}

	//delete myself here.
}

bool Node::Delete(Node * del, Node * parent)
{
	if(del->m_left == NULL)
	{
		Node * right = del->m_right;
		if(right)
		{
			del->m_data = right->m_data;
			del->m_left = right->m_left;
			del->m_right = right->m_right;

			right->m_left = NULL;
			right->m_right = NULL;

			right->m_data = -1;
			delete right;
			right->m_left = NULL;
			right->m_right = NULL;
			right = NULL;
		}
		else
		{
            if(parent && parent->m_left == del)
                parent->m_left = NULL;

            if(parent && parent->m_right == del)
                parent->m_right = NULL;

			del->m_data = -2;
			delete del;
			del->m_left = NULL;
			del->m_right = NULL;
			del = NULL;
		}
		return true;
	}
	else if(del->m_right == NULL)
	{
		Node * left = del->m_left;
		if(left)
		{
			del->m_data = left->m_data;
			del->m_left = left->m_left;
			del->m_right = left->m_right;


			left->m_data = -3;
			delete left;
			left->m_left = NULL;
			left->m_right = NULL;
			left = NULL;
		}
		else
		{ 
            if(parent && parent->m_left == del)
                parent->m_left = NULL;

            if(parent && parent->m_right == del)
                parent->m_right = NULL;

			del->m_data = -4;
			delete del;
			del->m_left = NULL;
			del->m_right = NULL;
			del = NULL;
		}

		return true;
	}
	else//用左子树的最右结点，也就是仅次于要删除结点的结点来替换。
	{
		Node * leftParent = del;
		Node * left = del->m_left;//Left肯定不为空。

		while(left && left->m_right)
		{	
			leftParent = left;
			left = left->m_right;
		}

		//现在Left是待删除结点的前驱结点,且右结点为空。。
		del->m_data = left->m_data;

		Node * leftleft = left->m_left;
		if(leftParent != del)
		{
			leftParent->m_right = leftleft; //left->m_right;
		}
		else
		{
			leftParent->m_left = leftleft;
		}

		left->m_left = NULL;
		left->m_right = NULL;

		left->m_data = -5;
		delete left;
		left->m_left = NULL;
		left->m_right = NULL;
		left = NULL;
		return true;
	}

}

bool Node::DeleteNode(int data, Node * parent)
{
	if(data == m_data)
		return Delete(this, parent);
	else if(data < m_data)
	{
		if(m_left)
			return m_left->DeleteNode(data, this);
		else
			return false;
	}
	else 
	{
		if(m_right)
			return m_right->DeleteNode(data, this);
		else
			return false;
	}
}

void Node::AddNode(Node * newNode)
{
	if(newNode->m_data < this->m_data)
	{
		if(this->m_left == NULL)
		{
			this->m_left = newNode;
		}
		else
		{
			this->m_left->AddNode(newNode);
		}
	}
	else
	{
		if(this->m_right == NULL)
		{
			this->m_right = newNode;
		}
		else
		{
			this->m_right->AddNode(newNode);
		}
	}

}

void Node::PrintNode()
{
	if(this->m_left != NULL)
		this->m_left->PrintNode();

	std::cout <<this->m_data << " ";

	if(this->m_right != NULL)
		this->m_right->PrintNode();

}

/////////////////////////////////////////////////////////////////////////////////////

BinarySortTree::BinarySortTree()
{
	m_root = NULL;
}

void BinarySortTree::Print()
{
	this->m_root->PrintNode();
}

bool BinarySortTree::Delete(int data)
{
	if(m_root == NULL)
		return false;
	else
		return m_root->DeleteNode(data, NULL);
}

void BinarySortTree::Add(int data)
{
	Node* newNode = new Node(data);
	if(m_root == NULL)
		m_root = newNode;
	else
		m_root->AddNode(newNode);
}

BinarySortTree::~BinarySortTree()
{
	if(m_root != NULL)
		delete m_root;

}
